import java.util.HashMap;
import java.util.Map;

/**
 * @author: gao
 * @create-date: 2025/3/15 19:56
 */

class Node{
    public int val;
    public Node next;
    public Node random;

    public Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node copyRandomList(Node head){
        Map<Node,Node> map = new HashMap<>();
        //第一遍遍历链表
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //第二遍遍历链表
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static void main(String[] args) {
        Node node1 = new Node(7);
        Node node2 = new Node(13);
        Node node3 = new Node(11);
        Node node4 = new Node(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        node1.random = node3;
        node2.random = node2;

        Solution solution = new Solution();
        solution.copyRandomList(node1);
        Node newHead = solution.copyRandomList(node1);
        System.out.println();
    }
}
